[프로그래머스] 전력망을 둘로 나누기

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var minDiff = 100
    func BFS(towerGraph: [[Bool]]) {
        var visited = Array(repeating: false, count: n + 1)
        var stack: [Int] = []
        stack.append(1)
        visited[1] = true
        while !stack.isEmpty {
            let checkPoint = stack.removeLast()
            for i in 1...n {
                if !visited[i] && towerGraph[checkPoint][i] {
                    visited[i] = true
                    stack.append(i)
                }
            }
        }
        let firstTowers = visited.filter{ $0 == true }.count
        let secondTowers = n - firstTowers
        let diff = abs(firstTowers - secondTowers)
        if diff < minDiff {
            minDiff = diff
        }
    }
    for i in 0..<wires.count {
        var cWires = wires
        cWires.remove(at: i)
        let towerGraphLine = Array(repeating: false, count: n + 1)
        var towerGraph: [[Bool]] = Array(repeating: towerGraphLine, count: n + 1)
        for wire in cWires {
            let startPoint = wire[0]
            let endPoint = wire[1]
            towerGraph[startPoint][endPoint] = true
            towerGraph[endPoint][startPoint] = true
        }
        BFS(towerGraph: towerGraph)
    }

    return minDiff
}

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var minDiff = 100
    func DFS(towerGraph: [[Bool]], lineIndex: Int, visited: inout [Bool], towerCount: inout Int) {
        for i in 1...n {
            if !visited[i] && towerGraph[lineIndex][i] {
                visited[i] = true
                towerCount += 1
                DFS(towerGraph: towerGraph, lineIndex: i, visited: &visited, towerCount: &towerCount)
            }
        }
    }
    for i in 0..<wires.count {
        var cWires = wires
        cWires.remove(at: i)
        let towerGraphLine = Array(repeating: false, count: n + 1)
        var towerGraph: [[Bool]] = Array(repeating: towerGraphLine, count: n + 1)
        for wire in cWires {
            let startPoint = wire[0]
            let endPoint = wire[1]
            towerGraph[startPoint][endPoint] = true
            towerGraph[endPoint][startPoint] = true
        }
        var visited = Array(repeating: false, count: n + 1)
        var towerCount = 0
        DFS(towerGraph: towerGraph, lineIndex: 1, visited: &visited, towerCount: &towerCount)
        let secondTowers = n - towerCount
        let diff = abs(towerCount - secondTowers)
        if diff < minDiff {
            minDiff = diff
        }
    }

    return minDiff
}

1. 전선을 하나 끊었을 떄 하나의 간선이 몇개 이어져있는지 확인
2. 전체 송전탑 - 이어진 송전탑 = 또 다른 송전탑의 갯수
3. 두개의 송전탑 개수의 차이 (절댓값)

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var connection = Array(repeating: Array(repeating: false, count: n+1), count: n+1)
    wires.forEach {
        connection[$0[0]][$0[1]] = true
        connection[$0[1]][$0[0]] = true
    }

    func countNodes(from root: Int, visited: [Bool]) -> Int {
        var count = 0
        var visited = visited

        func dfs(n: Int) {
            visited[n] = true
            count += 1
            connection[n].enumerated()
                .filter { $0.element == true && visited[$0.offset] == false }
                .forEach {
                    dfs(n: $0.offset)
                }
        }
        dfs(n: root)

        return count
    }

    // 임의의 노드에서, 그 노드포함해서 서브트리의 노드 개수를 구한다.
    var difference = Int.max
    var visited = Array(repeating: false, count: n+1)
    func travel(to node: Int) {
        visited[node] = true

        let subtreeA = countNodes(from: node, visited: visited)
        let subtreeB = n - subtreeA
        difference = min(difference, abs(subtreeA - subtreeB))


        connection[node].enumerated()
            .filter { $0.element == true && visited[$0.offset] == false }
            .forEach {
                travel(to: $0.offset)
            }
    }
    travel(to: 1)

    return difference
}